﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace SharpLZW
{
   public class LZWDecoder
   {
      public static string Compress(string uncompressed)
      {
         // build the dictionary
         Dictionary<string, int> dictionary = new Dictionary<string, int>();
         for (int i = 0; i < 256; i++)
            dictionary[string.FromCharCode(i)] = i;

         string w = string.Empty;
         List<int> compressed = new List<int>();

         for (int iChar = 0; iChar < uncompressed.Length; iChar++)
         {
            string c = uncompressed.Substr(iChar, 1);
            string wc = w + c;
            if (dictionary.ContainsKey(wc))
            {
               w = wc;
            }
            else
            {
               // write w to output
               compressed.Add(dictionary[w]);
               // wc is a new sequence; add it to the dictionary
               dictionary[wc] = dictionary.Count;
               w = c.ToString();
            }
         }

         // write remaining output if necessary
         if (!string.IsNullOrEmpty(w))
            compressed.Add(dictionary[w]);

         return EncodeCodeList( compressed);
      }

      public static string Decompress(string compressedAsString)
      {
         List<int> compressed = DecodeCodeList(compressedAsString);
         // build the dictionary
         Dictionary<int, string> dictionary = new Dictionary<int, string>();
         for (int i = 0; i < 256; i++)
            dictionary[i] = string.FromCharCode(i);

         string w = dictionary[compressed[0]];
         compressed.RemoveAt(0);
         StringBuilder decompressed = new StringBuilder(w);

         foreach (int k in compressed)
         {
            string entry = null;
            if (dictionary.ContainsKey(k))
               entry = dictionary[k];
            else if (k == dictionary.Count)
               entry = w + w.Substr(0, 1);

            decompressed.Append(entry);

            // new sequence; add it to the dictionary
            dictionary[dictionary.Count] = w + entry.Substr(0, 1);

            w = entry;
         }

         return decompressed.ToString();
      }

      static char[] lookupTable = new char[]
          {  
            'A','B','C','D','E','F','G','H','I','J','K','L','M','N',
            'O','P','Q','R','S','T','U','V','W','X','Y', 'Z',
            'a','b','c','d','e','f','g','h','i','j','k','l','m','n',
            'o','p','q','r','s','t','u','v','w','x','y','z',
            '0','1','2','3','4','5','6','7','8','9','+','/'
          };

      public static List<int> DecodeCodeList(string encoded)
      {
         Dictionary<int, int> codeValue = new Dictionary<int, int>();
         int idx = 0;
         foreach (char c in lookupTable)
         {
            codeValue[c.ToString().CharCodeAt(0)] = idx;
            idx++;
         }

         List<int> result = new List<int>();
         for (int i = 0; i < encoded.Length; i += 2)
         {
            int val1 = codeValue[encoded.CharCodeAt(i)];
            int val2 = codeValue[encoded.CharCodeAt(i+1)];
            result.Add(val1 + (val2 << 6));
         }
         return result;
      }

      public static string EncodeCodeList(List<int> lCodes)
      {

         string res = "";
         foreach (int element in lCodes)
         {
            int lsb = element & 0x3F;
            int msb = (element >> 6) & 0x3f;
            res += lookupTable[lsb].ToString() + lookupTable[msb].ToString();
         }
         return res;
      }

   }
}
